Was ist bad neighbors?

Bad Neighbors (Schlechte Nachbarn)

Das "Bad Neighbors"-Problem ist ein klassisches dynamisches Programmierungsbeispiel. Es behandelt folgendes Szenario:

Es gibt eine Reihe von Häusern in einer kreisförmigen Straße, jedes Haus enthält eine gewisse Menge Geld. Sie planen, einige dieser Häuser auszurauben, aber es gibt eine Einschränkung: Sie können keine zwei benachbarten Häuser ausrauben, da die Nachbarn sich gegenseitig alarmieren würden. Ziel ist es, die maximale Geldmenge zu finden, die Sie stehlen können, ohne Alarm auszulösen.

Hauptkonzepte:

• Dynamische Programmierung (DP): Die Lösung dieses Problems basiert typischerweise auf dynamischer Programmierung. DP ist eine Technik, bei der ein komplexes Problem in kleinere, überlappende Teilprobleme zerlegt und deren Lösungen gespeichert werden, um wiederholte Berechnungen zu vermeiden. [<a href="https://de.wikiwhat.page/kavramlar/Dynamische%20Programmierung">Dynamische Programmierung</a>]

• Überlappende Teilprobleme: Das Problem wird rekursiv in kleinere Teilprobleme zerlegt, die sich gegenseitig überlappen. Zum Beispiel kann die maximale Beute bis zum Haus i davon abhängen, ob Haus i-1 ausgeraubt wurde oder nicht.

• Optimal Substructure: Die optimale Lösung des gesamten Problems kann aus den optimalen Lösungen seiner Teilprobleme konstruiert werden.

Lösungsansatz:

Aufgrund der kreisförmigen Anordnung gibt es zwei Fälle zu berücksichtigen:

1. Das erste Haus wird ausgeraubt: In diesem Fall kann das letzte Haus nicht ausgeraubt werden.
2. Das erste Haus wird nicht ausgeraubt: In diesem Fall kann das letzte Haus ausgeraubt werden.

Für jeden Fall kann ein dynamisches Programmierungsschema verwendet werden, um die maximale Beute zu finden.

• Erstellen Sie ein Array dp, wobei dp[i] die maximale Beute bis zum Haus i darstellt.

• Die Basisfälle sind normalerweise:

  • dp[0] = values[0] (Beute des ersten Hauses, wenn es ausgeraubt wird)
  • dp[1] = max(values[0], values[1]) (Beute entweder des ersten oder zweiten Hauses)

• Iterieren Sie von Haus 2 bis zum Ende der Liste. Für jedes Haus i wählen Sie das Maximum zwischen:

  • Das aktuelle Haus i ausrauben und die maximale Beute bis Haus i-2 addieren (dp[i-2] + values[i]).
  • Das aktuelle Haus i nicht ausrauben und die maximale Beute bis Haus i-1 übernehmen (dp[i-1]).

• Nach der Iteration enthält dp[n-1] die maximale Beute.

Implementierung:

Die Implementierung beinhaltet typischerweise die oben beschriebene dynamische Programmierung mit Berücksichtigung der beiden Fälle (erstes Haus ausrauben vs. erstes Haus nicht ausrauben) und das Maximum der beiden Ergebnisse zurückgeben. Die Zeitkomplexität ist in der Regel O(n), und die Raumkomplexität kann durch die Verwendung von Variablen anstelle von Arrays reduziert werden.

Beispiel:

Angenommen, die Geldmengen in den Häusern sind values = [1, 2, 3, 1].

• Fall 1 (erstes Haus ausrauben): Häuser = [1, 2, 3]. Maximale Beute: 4 (1 + 3)
• Fall 2 (erstes Haus nicht ausrauben): Häuser = [2, 3, 1]. Maximale Beute: 3 (2 + 1)

Die maximale Beute ist also max(4, 3) = 4.

Variationen:

Es gibt Variationen dieses Problems, z. B. wenn die Häuser nicht kreisförmig angeordnet sind (einfachere lineare DP) oder zusätzliche Einschränkungen bestehen.